\renewcommand{\b}{{\bf b}}%bid action

\section{Expected Utility With Fair Tie-Breaking}\label{app:222}
\noindent
In this section we provide a computationally efficient procedure to compute the expected utility of an agent when there are $m=2$  simultaneous auctions, when using a fair tie breaking rule. This tie breaking rule means that, if $k$ players place the same bid in a particular auction, the probability of winning that auction is given by $1/k$. For convenience, we assume that both auctions have the same bid levels. Let $B$ denote the set of discrete bids in a particular auction. Then the set of actions $A=B \times B$ available to each bidder is given by bid pairs $\b = (b_1,b_2) \in A$, where $b_1$ and $b_2$ are the bids in auctions $1$ and $2$ respectively. 

Recall from Section~\ref{sec:sva} that the expected utility from playing an action $\b \in A$ is given by:
%
\begin{equation}
 \uet(\type,\b,\d)= \type \sum_{\eta\subseteq  K} \phi(\eta) \probwin(\b,\eta,\d)  - \cost(\b,\d) 
 \label{eq:eu2}
\end{equation}
In the following, we consider the left term first (which computes the expected value), followed by the right term (which computes the expected cost). Let $\Pr(W_i)$, $\Pr(W_i \cap W_j)$, and $\Pr(W_i \cap \bar{W_j})$ denote the probability of winning auction $i$, the probability of winning both auctions $i$ and $j$, and the probability of winning auction $i$ but not $j$. Then for $K=\{1,2\}$, we can rewrite the first term (ignoring the type) in equation \ref{eq:eu2} as follows:{
\begin{align*}
& \sum_{\eta\subseteq  \{1,2\}}\phi(\eta) \probwin(\b,\eta,\d)  = \alpha \probwin(\b,\{1\},\d)+\beta \probwin(\b,\{2\},\d) + \gamma \probwin(\b,\{1,2\},\d)\\
&\ \ = \alpha \Pr(W_1 \cap \bar{W_2}) + \beta \Pr(\bar{W_1} \cap {W_2}) + \gamma \Pr({W_1} \cap {W_2})\\
&\ \ = \alpha [ \Pr(W_{1}) - \Pr(W_{1} \cap W_{2})] + \beta[\Pr(W_{2}) - \Pr(W_{1} \cap W_{2})] + \gamma\Pr(W_{1} \cap W_{2})\\
&\ \ = \alpha\Pr(W_{1}) + \beta\Pr(W_{2})  + [\gamma - \alpha -\beta] \Pr(W_{1} \cap W_{2}),
\end{align*}
\noindent
where $\alpha= \phi(\{1\})$, $\beta=\phi(\{2\})$, and $\gamma = \phi(\{1,2\})$  as defined in Section~\ref{sec:sva}. From the equation, we can see that, in order to calculate the expected value, it is sufficient to calculate $\Pr(W_{1})$, $\Pr(W_{2})$, and $\Pr(W_{1} \cap W_{2})$. In the following, we derive these probabilities based on the action distribution $h$.

Let $H(\b)=\sum_{\b' \in A : b'_1 < b_1 \& b'_2 < b_2} h(\b')$. It is convenient to think of the function $H$ as a (multi-dimensional) cumulative distribution, where $h$ is the corresponding probability mass function.  In the following, we will also use the notation $H(b_1,b_2)=H(\b)$ and $h(b_1,b_2)=h(\b)$. Note that we define the inequalities in $H$ to be strict. In addition, we use $\leq b_i$ to denote a non-strict relationship for a particular auction. For example, $H(b_1, \leq b_2)=\sum_{\b' \in A : b'_1 < b_1 \& b'_2 \leq b_2} h(\b')$.\footnote{In practice, these functions can be implemented using a single look-up table, which can be computed in linear time and needs to be generated only once at the beginning of each FP iteration.}  Furthermore, let $X_1$ and $X_2$ denote random variables representing the bids placed by a bidder in auctions 1 and 2 respectively.\footnote{Note that these random variables consider the bids of one of the bidders, and not {\it all} bidders. Since bidders are assumed to be symmetric it does not matter which particular one. Also, note that the variables are {\it interdependent} since the actions specify bid pairs. Therefore, we cannot assume that, e.g., $\Pr(X_1 < b_1 \cap X_2 < b_2)=\Pr(X_1 < b_1) \cdot \Pr(X_2 < b_2)$.} We can then use the functions $H$ and $h$ to define the following events:
\begin{enumerate}
\item $\Pr(X_1 < b_1 \cap X_2 < b_2)=H(b_1,b_2)$: win both auctions,
\item $\Pr(X_1 = b_1 \cap X_2 = b_2)=h(b_1,b_2)$: tie in both auctions,
\item $\Pr(X_1 = b_1 \cap X_2 < b_2)=H(\leq b_1,b_2) - H(b_1,b_2)$: tie in auction $1$ and win auction $2$,
\item $\Pr(X_1 < b_1 \cap X_2 = b_2)=H(b_1,\leq b_2) - H(b_1,b_2)$: win auction $1$ and tie in auction $2$,
\item $\Pr(X_1 > b_1 \cap X_2 > b_2)=[1-H(\leq b_1,\leq b_2)]$: lose both auctions.
\end{enumerate}

Note that the above events are mutually exclusive and always sum to one. If we define $H_i(b_i)=\sum_{\b' \in A : b'_i < b_i} h(\b')$ to be the cumulative bid distribution for a particular auction, we can similarly derive mutually exclusive events for a single auction:
\begin{enumerate}
\item $\Pr(X_i < b_i)=H_i(b_i)$: win auction $i$,
\item $\Pr(X_i = b_i)=H_i(\leq b_i)-H_i(b_i)$: tie in auction $i$,
\item $\Pr(X_i > b_i)=[1-H_i(\leq b_i)]$: lose auction $i$.
\end{enumerate}

The above provides the probabilities of certain events for a single other opponent. However, since there are $n-1$ opponents, we need to calculate the distribution of the first-order statistic. When the bids are continuous, this is straightforward since (for example) $\Pr(X_i < b_i)=\Pr(X_i \leq b_i)$, and so $\Pr(W_i)=\Pr(X_i < b_i)^{n-1}=H_i(b_i)^{n-1}$. However, in the case of discrete bids, we also have to account for the tie breaking rule. For the single-auction case, $\Pr(W_i)$ becomes:\footnote{Note that this is similar to Example~\ref{example:fpa} in Section~\ref{sec:model}, except that the distribution also takes into account the fact that the actions are joint bids over multiple auctions.}
%
\begin{equation}
\Pr(W_i) = \sum_{x=0}^{n-1}\frac{1}{x+1}{n-1 \choose x}\Pr(X_i = b_i)^x \Pr(X_i< b_i)^{n-1-x}
\end{equation}
%
In the case of two auctions, this becomes much more complex since we need to enumerate over three possible events where ties occur: ties can occur in auction 1 only, in auction 2 only, or in both auctions. In the following, let $x$ denote the number of bidders that correspond to first event, $y$ to the second event, and $z$ to the third event.  Then, $\Pr(W_1 \cap W_2)$ becomes:
{\small
\begin{align}
\label{eq:probwin2auctions}
& \Pr(W_1 \cap W_2)=\\
& \sum_{x=0}^{n-1}\sum_{y=0}^{n-1-x}\sum_{z=0}^{n-1-x-y}{n-1 \choose x}{n-1-x \choose y}{n-1-x-y \choose z}\frac{1}{x+z+1}\frac{1}{y+z+1}\times \nonumber \\
& \Pr(X_{1} = b_{1} \cap X_{2} < b_{2})^x \Pr(X_{1} < b_{1} \cap X_{2} = b_{2})^y \Pr(X_{1} = b_{1} \cap X_{2} = b_{2})^z \times \nonumber\\
&\Pr(X_{1} < b_{1} \cap X_{2} < b_{2})^{n-1-x-y-z} \nonumber
\end{align}
}
%Letting $\nb{x}$ denote the next bid above $x$ (or infinity if $x$ is the highest bid), 
%Letting $\epsilon$ be any positive number that is less than the difference between any two consecutive bids, we express the probabilities in this equation through $H_{\mu2}$ and $h_{\mu\nu}$
%{\small
%\begin{align*}
%& \Pr(W_\mu \cap W_2)=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1-x}\sum_{z=0}^{n-1-x-y}{n-1 \choose x}{n-1-x \choose y}{n-1-x-y \choose z}\frac{1}{x+z+1}\frac{1}{y+z+1}\times\\
%& [\Pr(X_{\mu} < \nb{b_{\mu}} \cap X_{2} < b_{2}) - \Pr(X_{\mu} < b_{\mu} \cap X_{2} < b_{2})]^x [\Pr(B_{\mu} < b_{\mu} \cap X_{2} < \nb{b_{2}}) - \Pr(X_{\mu} < b_{\mu} \cap X_{2} < b_{2})]^y \Pr(X_{\mu} = b_{\mu} \cap X_{2} = b_{2})^z \Pr(X_{\mu} < b_{\mu} \cap X_{2} < b_{2})^{n-1-x-y-z}
%& [H_{\mu2}(b_{\mu}+\epsilon,b_{2}) - H_{\mu2}(b_{\mu},b_{2})]^x [H_{\mu2}(b_{\mu},b_{2}+\epsilon) - H_{\mu2}(b_{\mu},b_{2})]^y h_{\mu2}(b_{\mu},b_{2})^z %H_{\mu2}(b_{\mu},b_{2})^{n-1-x-y-z}
%\end{align*}
%}
\noindent
The above completes the computation of the expected value. We now show how to compute the final component of equation~\ref{eq:eu2}, the expected cost $cost(\b,h)$. We note that, unlike the probability of winning $\eta$ out of $K$ auctions, we can consider the expected costs for each auction separately thanks to linearity of expectation. Specifically, $cost(\b,h)=cost_1(b_1,h)+cost_2(b_2,h)$, where $cost_i(b_i,h)$ is the expected cost of auction $i$ when bidding $b_i$ in this auction. From~\cite{krishnabook} we know that for a single second-price auction, in the continuous case, the expected payment is equal to: $cost_i(b_i,h)=\int_0^{b_i} y g(y)dy$, where $g(y)$ is the density function of the first-order statistic of the bid distribution. However, with discrete bids, we need to consider two cases separately: when the second-highest bid in auction $i$ is strictly less than $b_i$, then the bidder wins for sure. On the other hand, if the second-highest bid is equal to $b_i$, the probability of winning depends on the tie breaking rule. This results in the following equation:
\begin{equation}
cost_i(b_i,h)= \sum_{x \in B | x < b_i} x \left[(H_i(\leq x))^{n-1}-(H_i(x))^{n-1}\right] 
+ b_i \left[ \Pr(W_i) - (H_i(x))^{n-1}\right],
\end{equation}
\noindent where $[(H_i(\leq x))^{n-1}-(H_i(x))^{n-1}]$ is the marginal bid distribution and corresponds to $g(y)$ in the continuous case. This completes the expected utility calculation.

As can be seen, due to the tie breaking rule, calculating the expected utility is computationally demanding. In particular, Equation~\ref{eq:probwin2auctions} considers all combination of ties which can simultaneously occur in 2 auctions (note that we cannot consider the auctions independently as the bid probabilities in the two auctions are correlated), and its computation is in the order of $O(n^3)$. This complexity increases rapidly for more than 2 auctions. Hence, in the next section we consider a way to approximate the expected utility concerning the tie breaking. 

\subsection{Approximate Tie Breaking}
\label{sec:approxtie}
\noindent The above shows that, while computing the expected cost component of the expected utility is relatively easy since this can be done independently for each auction, the same is not true for calculating the expected value, which involves calculating the probability of winning every subset of auctions. In particular, the tie breaking rule increases the computation required and does not scale well with the number of bidders and the number of auctions. To address this problem, in this section we present an approximated tie breaking rule, which has been used in some of the experiments in this paper (specifically, in Section~\ref{sec:convergence}).

In more detail, the approximation is based on the observation that, in the case of 2 auctions, the exact probability of winning is always between $H(\leq b_1,\leq b_2)^{n-1}$ and $H(b_1,b_2)^{n-1}$. The first term over-estimates the probability of winning, whereas the second term underestimates it. Given this, the approximate probability of winning both auction is defined as:
\begin{equation}
\tilde{\Pr}(W_1 \cap W_2) = \lambda H(\leq b_1,\leq b_2)^{n-1} + (1-\lambda) H(b_1,b_2)^{n-1},
\end{equation}
where $\lambda$ is a parameter which can be tuned. In the experiments, we used the value $\lambda=1/3$ which performed well in general compared to the exact solution, although we did not excessively tune it. Note that this approach can also be applied to a single auction, and more than 2 auctions.



%For a given bid pair $b$ and distribution of bids $H_{\mu2}$ we define 
%\begin{itemize}
%\item $S_{\mu}$ - win item $\mu$ without a tie
%\item $T_{\mu}$ - win item $\mu$ after tying
%\item $W_{\mu} = S_{\mu} \cup T_{\mu}$ - win item $\mu$
%\end{itemize}
%All events are defined analogously for winning the item $2$ and winning both items $\mu$ and $2$. We calculate the probability of each event below.
%{\small\begin{align*}
%& \Pr(S_{\mu}) = H_{\mu}(b_{\mu})^{n-1}\\
%& \Pr(S_{\mu2}) = H_{\mu2}(b)^{n-1}\\
%& \Pr(T_{\mu}) = \sum_{x=1}^{n-1}\frac{1}{x+1}{n-1 \choose x}h_{\mu}^x(b_{\mu})H_{\mu}^{n-1-x}(b_{\mu})\\
%& \Pr(W_{\mu}) = \Pr(S_{\mu}) + \Pr(T_{\mu})
%& \Pr(W_{\mu2}) = \Pr(S_{\mu2}) + \Pr(T_{\mu} \cap S_{2}) + \Pr(T_{2} \cap S_{\mu}) + \Pr(T_{\mu} \cap T_{2})
%\end{align*}}

%The expected utility of an agent submitting the bid pair $b$ is%when the distribution of bid pairs of any other bidder is $P_{AB}$
%{\small\begin{align}
%& \uet(\theta_i,b,h) = \theta_i \Pr[\text{win}] - E[\text{cost}]\nonumber\\
%& \uet(\theta_i,b,h) = \theta_i \left(\alpha\Pr(W_{\mu} \cap \bar{W_{2}}) + \beta\Pr(W_{2} \cap \bar{W_{\mu}}) + \gamma\Pr(W_{\mu} \cap W_{2})\right)  - c(b,h)\nonumber\\
%& =  \theta_i \left(\alpha[\Pr(W_{\mu}) - \Pr(W_{\mu} \cap W_{2})] + \beta[\Pr(W_{2}) - \Pr(W_{\mu} \cap W_{2})] + \gamma\Pr(W_{\mu} \cap W_{2})\right) - c(b,h)\nonumber\\
%& =  \theta_i \left(\alpha\Pr(W_{\mu}) + \beta\Pr(W_{2})  + \Pr(W_{\mu} \cap W_{2})[\gamma - \alpha -\beta] \right) - c(b,h) \label{eq:exputilapp}
%\end{align}}
%where $c(b,h)$ denotes the expected payment. The expected payment for good $\mu$ is
%{\small\begin{align*}
%& c_{\mu}(b_{\mu},h_{\mu}) = H_{\mu}(b_{\mu})^{n-1}E[Z_{\mu}|Z_{\mu} < b_{\mu}] + \Pr(T_{\mu})\Pr(Z_{\mu}=b_{\mu})b_{\mu} = \\
%& c(b,h) = \Pr(\mu)E[\text{highest bid on $\mu$ among the other bidders} \mid \text{$b_{\mu}$ is the highest bid}] \\
%& + \Pr(2)E[\text{highest bid on $2$ among the other bidders} \mid \text{$b_{2}$ is the highest bid}]
%\end{align*}}
%The total expected payment is 
%{\small\begin{align*}
%& c(b,h) = c_{1}(b_{1},h_{1}) + c_{2}(b_{2},h_{2})
%\end{align*}}
%Combining the expected value with the expected payment we get
%\begin{align}
%& \uet(\theta_i,b,h) =  \theta_i \left(\alpha\Pr(W_{X_}) + \beta\Pr(W_{2})  + \Pr(W_{1} \cap W_{2})[\gamma - \alpha -\beta] \right) - c(b,h) \label{eq:ut}
%\end{align}

\subsection{Two Bidders}
\noindent
Here, we consider a special case of the equations with the exact tie breaking rule for $n=2$. Instantiating Equation~\ref{eq:probwin2auctions} for $n=2$, this results in the following 4 combinations of $(x,y,z)$: $(0,0,0)$; $(0,0,1)$; $(0,1,0)$;$(1,0,0)$. Expanding the equation we get
{\small
\begin{align*}
& \Pr(W_1 \cap W_2)= \\
& \underbrace{H(b_{1},b_{2})}_{0,0,0} + 
\underbrace{\frac{1}{4}h(b_{1},b_{2})}_{0,0,1} + 
\underbrace{\frac{1}{2}[H(b_{1},b_{2}+\epsilon) - H(b_{1},b_{2})]}_{0,1,0} + 
\underbrace{\frac{1}{2}[H(b_{1}+\epsilon,b_{2}) - H(b_{1},b_{2})]}_{1,0,0} = \\
& \frac{1}{4}h(b_{1},b_{2}) + \frac{1}{2}H(b_{1},\leq b_{2}) + \frac{1}{2}H(\leq b_{1},b_{2})
\end{align*} 
}
In the case of a single auction, we get:
\begin{equation}
\Pr(W_{i}) = H_{i}(b_i)+\frac{1}{2} \left[H_{i}(\leq b_i)-H_{i}(b_i)\right]=\frac{1}{2} \left[H_{i}(\leq b_i) + H_{i}(b_i)\right]
\end{equation}
%
Instantiating Equation~\ref{eq:eu2}, we get 
{\small\begin{align*}
& u(\theta,\b,h) = \theta \left(\alpha\Pr(W_{1}) + \beta\Pr(W_{2})  + (\gamma - \alpha -\beta)\Pr(W_{1} \cap W_{2}) \right) - cost(\b,h)\\
& = \theta (\alpha \frac{1}{2} \left[H_{1}(\leq b_1) + H_{1}(b_1)\right] + \beta \frac{1}{2} \left[H_{2}(\leq b_2) + H_{2}(b_2)\right] + \\
& (\gamma - \alpha -\beta)[\frac{1}{4}h(b_{1},b_{2}) + \frac{1}{2}H(b_{1},\leq b_{2}) + \frac{1}{2}H(\leq b_{1},b_{2})]) - cost(\b,h)
\end{align*}}

The expected payment for auction $i$ simplifies to
\begin{equation*}
cost_{i}(b_{i},h) = \left(\sum_{x \in B \mid x < b_{i}} x \left[H_{i}(\leq x)-H_{i}(x)\right] \right) +  \frac{1}{2} b_i \left[H_{i}(\leq b_{i})- H_i(b_i)\right]
\end{equation*}

\subsection{Two Bids}
\noindent
Further assume the only available bids levels are $B=\{0,1\}$. This results in 4 possible bid pairs as actions. We denote the probability of encountering each bid pair, and the corresponding cumulative distribution as follows:
\begin{table}[h!]
\begin{tabular}{lll}
 $h(0,0) = x$       &   $H(0,0) =0$ & \\
 $h(1,0) = y$       &   $H(1,0) =0$ & $H(\leq 1,1) = x+y$ \\
 $h(0,1) = z $      &   $H(0,1) =0$ & $H(1,\leq 1) = x+z$\\ 
 $h(1,1) = 1-x-y-z$ &   $H(1,1) =x$ & $H(\leq 1,\leq 1) = 1$
\end{tabular}
\end{table}

The corresponding  distributions for single auctions are:
\begin{table}[h!]
\begin{tabular}{lll}
$H_{1}(0) = 0$ & $ H_{1}(1) = x+z$ & $H_{1}(\leq 1)=1$\\
$H_{2}(0) = 0$ & $H_{2}(1) = x+y$ & $H_{2}(\leq 1) = 1$
\end{tabular}
\end{table}

%Using the equations below 
%{\small\begin{align*}
%& u(\theta_i,b,h) = \theta_i (\alpha[H_{1}(b_{1}) + \frac{1}{2}h_{1}(b_{1})] + \beta[H_{2}(b_{2}) + \frac{1}{2}h_{2}(b_{2})] + \\
%& (\gamma - \alpha -\beta)[\frac{1}{4}h_{12}(b_{1},b_{2}) + \frac{1}{2}H_{12}(b_{1},b_{2}+\epsilon) + \frac{1}{2}H_{12}(b_{1}+\epsilon,b_{2})]) - c(b,h)\\
%& c(b,h) = \left(\sum_{\beta \in X_{1} \mid \beta < b_{1}}h_{1}(\beta)\beta\right) + \frac{1}{2}h_{1}(b_{1})b_{1} + \left(\sum_{\beta \in X_{2} \mid \beta < b_{2}}h_{2}(\beta)\beta\right) + %\frac{1}{2}h_{2}(b_{2})b_{2}
%\end{align*}}
This then results in the following expected utility for each action:
%%%use these equations
%\begin{align*}
%& u(\theta_i,(0,0)) = \theta_i [\alpha\frac{1}{2}(x+z) + \beta\frac{1}{2}(x+y) + (\gamma - \alpha -\beta)\frac{1}{4}x] = \theta_i [\alpha(\frac{1}{4}x+\frac{1}{2}z) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x]\\
%& u(\theta_i,(1,0)) = \theta_i [\alpha(x+z + \frac{1}{2}(1-x-z)) + \beta\frac{1}{2}(x+y) + (\gamma - \alpha -\beta)(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z) = \\
%&  \quad \theta_i [\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z)\\
%& u(\theta_i,(0,1)) = \theta_i [\alpha\frac{1}{2}(x+z) + \beta(x+y + \frac{1}{2}(1-x-y)) + (\gamma - \alpha -\beta)(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y) =\\
%&  \quad \theta_i [\alpha\frac{1}{4}z + \beta(\frac{1}{2}y -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
%
%& u(\theta_i,(1,1)) = \theta_i [\alpha(x + z + \frac{1}{2}(1 - x - z)) + \beta(x+y + \frac{1}{2}(1-x-y)) + \\
%& \quad (\gamma - \alpha -\beta)(\frac{1}{4}(1-x-y-z) + \frac{1}{2}(x + z) + \frac{1}{2}(x + y))] - \frac{1}{2}(1-x-y) - \frac{1}{2}(1-x-z) =\\
%\end{align*}
{\small
\begin{align*}
& \uet(\theta,(0,0),h) = \theta [\alpha(\frac{1}{4}x+\frac{1}{2}z) + \beta(\frac{1}{4}x+\frac{1}{2}y) + \gamma\frac{1}{4}x] \\
& \uet(\theta,(1,0),h) = \theta [\alpha(- \frac{1}{4}y + \frac{1}{2}z + \frac{1}{2}) + \beta\frac{1}{4}y + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z)\\
& \uet(\theta,(0,1),h) = \theta [\alpha\frac{1}{4}z + \beta(\frac{1}{2}y -\frac{1}{4}z + \frac{1}{2}) + \gamma(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& \uet(\theta,(1,1),h) = \theta [\alpha(-\frac{1}{4}x - \frac{1}{4}y + \frac{1}{4}z + \frac{1}{4}) + \beta(-\frac{1}{4}x + \frac{1}{4}y - \frac{1}{4}z + \frac{1}{4}) + \gamma(\frac{3}{4}x + \frac{1}{4}y + \frac{1}{4}z + \frac{1}{4})] \\
& \quad \quad \quad \quad \quad \quad - 1 + x + \frac{1}{2}(y+z)
\end{align*}
}

\subsection{Identical Auctions}
\noindent
The auctions are identical when $\alpha=\beta$. Since we do not restrict $\gamma$, we can without loss of generality set $\alpha=\beta=1$. 
{\small
\begin{align*}
& \uet(\theta,(0,0),h) = \theta [\frac{1}{2}x+\frac{1}{2}y+ \frac{1}{2}z + \gamma\frac{1}{4}x] \\
& \uet(\theta,(1,0),h) = \theta [\frac{1}{2}z + \frac{1}{2}  + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-z)\\
& \uet(\theta,(0,1),h) = \theta [\frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}z + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& \uet(\theta,(1,1),h) = \theta [(-\frac{1}{2}x	+ \frac{1}{2}) + \gamma(\frac{3}{4}x + \frac{1}{4}y + \frac{1}{4}z + \frac{1}{4})] - 1 + x + \frac{1}{2}(y+z)
\end{align*}
}
We are interested in utilities under symmetric equilibria. In all such equilibria the probabilities of playing bids $(1,0)$ and $(0,1)$ are the same: i.e., $y=z$.
{\small
\begin{align*}
& \uet(\theta,(0,0),h) = \theta [\frac{1}{2}x+ y+ \gamma\frac{1}{4}x] \\
& \uet(\theta,(1,0),h) = u(\theta,(0,1)) = \theta [\frac{1}{2}y + \frac{1}{2}  + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)\\
& \uet(\theta,(1,1),h) = \theta [(-\frac{1}{2}x	+ \frac{1}{2}) + \gamma(\frac{3}{4}x + \frac{1}{2}y + \frac{1}{4})] - 1 + x + y
\end{align*}
}


\section{Proof of Lemma~\ref{lem:ue}}
\label{app:lemmaproof}
%\begin{lemma}
%Given a set of available actions $A = \{a_1\preceq \ldots \preceq a_m\}$, the pair $(A'=\{a'_1 \preceq \ldots \preceq a'_{m'}\},\i)$ is a pure strategy best response to the action distribution $h$ if and only if the following equations are satisfied:
%\begin{align*}
%& A' \subseteq A \\
%& 0 < \i_1 < \ldots < \i_{m'-1} < 1 \\
%& \uet(\i_{j},a'_j,h) = \uet(\i_{j},a'_{j+1},h) \quad \forall\ 1 \le j \le m'-1 \\
%& \uet(0,a'_1,h) \ge \uet(0,a_k,h) \quad \forall\  a_k \prec a'_1 \\
%& \uet(\i_{j},a'_j,h) \ge \uet(\i_{j},a_k,h) \quad \forall\ 1 \le j \le m' \quad a'_j\prec a_k\prec a'_{j+1} 
%\end{align*}
%where $\i_0 = 0$, $\i_{m'} = 1$, and $\a'_{m'+1}$ is a dummy action (i.e., it does not appear in $A$) and has a slope %above $a_{m}$ (this dummy action is used in Equation~(\ref{eq:utineq2})).
%\end{lemma}
\begin{proof}
We need to show that $(A',\i)$ specifies an upper envelope of the utility lines $\{\uet(\type,\a_j,\d)\}_{j=1}^{m}$. 
%Equation~(\ref{eq:subset}) limits attention to only utility lines $\{\uet(\type;\a_j,\d)\}_{j=1}^{m}$, while Equation~(\ref{eq:const}) guarantees $\i$ provides a valid partition of the type space $\Theta=[0,1]$. 
Equations~(\ref{eq:subset}) and~(\ref{eq:const}) simply limit attention to a convenient best-response representation, which, as we noted is without loss of generality.
A pair $(A',\i)$ satisfying these two equations defines a function: 
\begin{align*}
& g(\type) = \uet(\type,a'_j,h) \quad \text{where } j\mid \type \in [\i_{j-1}, \i_{j}]
\end{align*}
First we show the ``if" direction. Equation~(\ref{eq:ut}) guarantees that the function is continuous: at each {\em intersection} point $\i_j$ (where the function $g(\type)$ switches from one utility line to another), the values of adjacent utility lines are the same. 
This function is an upper envelope if no utility line lies above it. Since each equation is a line, it is sufficient to check that at each intersection point $c_j$ the value of $g(\type)$ is at least as high as the value of all other utility lines. In fact, it is enough to check each of the lines $A \setminus A'$ at exactly one $c_j$ as we argue next.
For a line $a_k \in A \setminus A'$ we can uniquely identify $a'_j$ and $a'_{j+1}$ such that $a'_j \prec a_k \prec a'_{j+1}$. Equation~(\ref{eq:utineq2})\footnote{Equation~(\ref{eq:utineq1}) covers the special case of $a'_1$, the first action in $A'$: the value of $g(\type)$ at $0$ is checked to be at least as high as the values of all utility lines with slopes {\em below} $a'_1$.} checks that the utility from playing $a_k$ at the type $c_j$ is below the utility from playing $a'_j$ (which, by Equation~\ref{eq:ut}, is the same as the utility from playing $a'_{j+1}$). Formally, we have:
\begin{align*}
& \uet(c_j,a_k,h)  \le \uet(c_j,a'_j,h) = \uet(c_j,a'_{j+1},h)
\end{align*}
We first consider: 
\begin{align}
& \uet(c_j,a_k,h)  \le \uet(c_j,a'_{j+1},h) \label{eq:whatev0}
\end{align}
Since two lines intersect at most once, and after the intersection, the line with the higher slope is on top,
Equations~(\ref{eq:ut}) together with $a'_1 \prec \ldots \prec a'_{m'}$ imply:
\begin{align*}
& \uet(c_{j+1},a'_{j+1},h)  \le \uet(c_{j+1},a'_{j+2},h) \quad \forall \theta \ge c_{j+1}\\
& \uet(c_{j+2},a'_{j+2},h)  \le \uet(c_{j+2},a'_{j+3},h) \quad \forall \theta \ge c_{j+2}\\
& \ldots\\
& \uet(c_{m'-1},a'_{m'-1},h)  \le \uet(c_{m'-1},a'_{m'},h) \quad \forall \theta \ge c_{m'-1}
\end{align*}
Recalling that $a_k \prec a'_{j+1}$ and applying the argument above to Equation~(\ref{eq:whatev0}), we get:
%Suppose the utility from playing $a_k \prec a'_j$ when the type is $c_j$ is below the utility from playing $a'_j$
\begin{align}
& \uet(\theta,a_k,h)  \le \uet(\theta,a'_{j+1},h) \quad \forall \theta \ge c_{j}  \label{eq:whateva}
\end{align}
Noting that $\uet(c_j,a'_{j+1},h) \le \uet(c_{j+1},a'_{j+1},h)$ and combining Equation~(\ref{eq:whateva}) with the inequalities above, we get: 
\begin{align}
& \uet(c_i,a_k,h) \le \uet(c_i,a'_i,h) \quad \forall i \ge j+1\label{eq:alla}
\end{align}
In other words, if a utility line with a smaller slope than $a'_{j+1}$ is below $a'_{j+1}$ at $c_j$, then it is also below $g(\type)$ for all types above $c_j$. It remains to consider the case of $a'_j \prec a_k$: 
\begin{align}
& \uet(c_j,a_k,h)  \le \uet(c_j,a'_{j},h) \label{eq:whatev0.5}
\end{align}
Analogously to the argument above, before two lines intersect, the one with the lower slope is above the one with the higher slope. Hence, Equation~(\ref{eq:ut}) and $a'_1 \prec \ldots \prec a'_{m'}$ imply:
\begin{align*}
%& \uet(c_{j},a'_{j+1},h)  \le \uet(c_{j},a'_{j},h) \quad \forall \theta \le c_{j}\\
& \uet(c_{j-1},a'_{j},h)  \le \uet(c_{j-1},a'_{j-1},h) \quad \forall \theta \le c_{j-1}\\
& \uet(c_{j-2},a'_{j-1},h)  \le \uet(c_{j-2},a'_{j-2},h) \quad \forall \theta \le c_{j-2}\\
& \ldots\\
& \uet(c_1,a'_{2},h)  \le \uet(c_1,a'_{1},h) \quad \forall \theta \le c_{1}
\end{align*}
Recalling that $a_k \prec a'_{j+1}$, and applying the argument above to Equation~(\ref{eq:whatev0.5}), we get:
%Suppose the utility from playing $a_k \prec a'_j$ when the type is $c_j$ is below the utility from playing $a'_j$
\begin{align}
& \uet(\theta,a_k,h)  \le \uet(\theta,a'_{j},h) \quad \forall \theta \le c_{j}  \label{eq:whatevb}
\end{align}
Noting that $\uet(c_{j-1},a_k,h)  \le \uet(c_{j-1},a'_{j},h)$ and combining Equation~(\ref{eq:whatevb}) with the inequalities above, we get: 
\begin{align}
& \uet(c_i,a_k,h) \le \uet(c_i,a'_i,h) \quad \forall i \le j \label{eq:allb}
\end{align}
By Equations~(\ref{eq:alla}) and~(\ref{eq:allb}), the line for $a_k$ is below $g(\theta)$ at all intersection points $c_i$ and therefore at all types. This argument applies to all lines $a_k$, proving that $(A',\i)$ is a best response.

%Equations~(\ref{eq:utineq2}) check that at the highest type for which $a'_j$ is played (equivalently, the lowest type for which $a'_{j+1}$ is played, equivalently at $c_j$), the value of $g(\type)$ is at least as high as the values of the utility lines with slopes between $a'_j$ and $a'_{j+1}$. Note that each of the lines $A \setminus A'$ is checked at exactly one $c_j$.\footnote{Equation~(\ref{eq:utineq1}) covers the special case of $a'_1$, the first action in $A'$: the value of $g(\type)$ at $0$ is checked to be at least as high as the values of all utility lines with slopes {\em below} $a'_1$.} For contradiction, suppose there is a line that lies above $g(\type)$ for some $\theta$. Then, it either lies above $g$ for all $\theta$ or crosses $g$. The first case can be rules out immediately as each line $A \setminus A'$ lies below $g$ for some $c_j$ as guaranteed by Equations~(\ref{eq:utineq1}) or~(\ref{eq:utineq2}). Let us consider the case of a line crossing $g$ at $\theta'$. Again, it must lie below $g$ for some $c_j$.

The ``only if" part of the proof is trivial: violating Equation~(\ref{eq:ut}) for any $j$ results in a discontinuous function, while a best response must be continuous. Furthermore, if any of the inequalities in Equations~(\ref{eq:utineq1}) or~(\ref{eq:utineq2}) do not hold, then a better response is available, again contradicting the best response.
\end{proof}



\section{Derivation of Equilibrium Strategies}\label{app:derivation}
\noindent
Here we provide a derivation of the equilibria discussed in Section~\ref{sec:simauctions} and plotted in Figure~\ref{fig:eq}. 
%Recall that the equilibria were  derived for a special case of identical auctions,  two bidders, four bid pairs, and uniform distribution of types $U(0,1)$. Specializing the expected utility defined in Equation~\ref{eq:ut} with $\alpha=\beta=1$ we get 
%\begin{align*}
%& u(\theta_i,b,h) = \theta_i \left(\Pr(W_{1}) + \Pr(W_{2})  + \Pr(W_{1} \cap W_{2})[\gamma - 2] \right) - c(b,h)
%\end{align*}
The equilibrium bid distribution for a symmetric equilibrium $(A',\i)$ is 
{\small\begin{align*}
& h(b_{\pi(j)};\i) = F(\i_j)-F(\i_{j-1}) \quad \forall\ 1 \le j \le |A'|\\
& h(b_j;\i) = 0 \quad \forall b_j \notin A'
\end{align*}}
Plugging in the uniform distribution of types we get 
{\small\begin{align*}
& h(b_{\pi(j)};\i) = \i_j-\i_{j-1} \quad \forall\ 1 \le j \le |A'|
\end{align*}}
As before, we use $x,y,y,1-x-2y$ to denote $h(0,0)$, $h(1,0)$, $h(0,1)$, and $h(1,1)$ respectively. 
%In a symmetric equilibrium $(A',a)$, probabilities for the bids in $B'$ are given by the parameters $a$ as shown in the equation above; the probabilities of playing the bids $B\setminus B'$ are zero. %For example, for $B' = \{(0,0)\ (1,0)\}$, we have
%Invoking Lemma~\ref{}, for $B' = \{(0,0)\ (1,1)\} = \{b_1,b_4\}$ to be an equilibrium the following inequalities must hold
%Note that after replace probabilities $x$ and $y$, the expected utility becomes a function of $a$.

%Recall that the bids $(0,1)$ and $(1,0)$ are played with equal probability on one continuous interval and we only talk about the bid $(1,0)$ in the derivations.
We present a complete derivation for $A' = \{(0,0)\ (1,0)\}$. The piecewise linear strategy $(A',\i)$ consists of 2 intervals: bid $(0,0)$ is played on the interval $\theta \in [0,\i_1]$, bid $(1,0)$ on the interval $\theta \in [\i_1,1]$. The strategy is given by a parameter $0 < \i_1 < 1$.
Using Lemma~\ref{lem:ue}, $(A',\i)$ must satisfy 
{\small\begin{align}
& u(\i_1,(0,0),h(\cdot;\i)) = u(\i_1,(1,0),h(\cdot;\i))\\
& u(1,(1,0),h(\cdot;\i)) \ge u(1,(1,1),h(\cdot;\i))\label{eq:b1b2ineq}\\
& h(0,0) = x = \i_1 \quad\quad h(1,0) = h(0,1) = y = \frac{1-\i_1}{2} \quad\quad h(1,1) = 0 \label{eq:prob1}
\end{align}}
Since we fixed $A'$, the only degrees of freedom are $\i$ and $\gamma$. We solve the first equation for $\i_1$ as a function of $\gamma$ and plug it into the second inequality to find the range of $\gamma$ supporting the equilibrium $(A',\i)$.

%Note that since $b_1 \in B'$, the inequalities~(\ref{eq:utineq1}) are empty. The only bid that is not part of $B'$ is $(1,1)$ resulting in the only inequality above corresponding to inequality~(\ref{eq:utineq2}). 
Expanding $u(\i_1,(0,0),h(\cdot;\i)) = u(\i_1,(1,0),h(\cdot;\i))$, we obtain
{\small\begin{align*}
& \i_1 [\frac{1}{2}x+ y+ \gamma\frac{1}{4}x] = \i_1 [\frac{1}{2}y + \frac{1}{2}  + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y)
\end{align*}}
Replacing $x$ and $y$ according to Equations~\ref{eq:prob1} and simplifying we obtain
{\small\begin{align*}
%& \i_1 [\frac{1}{2}\i_1+ \frac{1-\i_1}{2}+ \gamma\frac{1}{4}\i_1] = \i_1 [\frac{1}{2}\frac{1-\i_1}{2} + \frac{1}{2}  + \gamma(\frac{1}{4}\frac{1-\i_1}{2} + \frac{1}{2}\i_1)] - \frac{1}{2}(1-\i_1-\frac{1-\i_1}{2})
& \i_1^2(\gamma-2) + \i_1(\gamma+4) - 2 = 0
\end{align*}}
The roots of the quadratic equation are
{\small\begin{align*}
& \i_1 = \frac{-\gamma-4 \pm \sqrt{\gamma^2 + 16\gamma}}{2(\gamma-2)}
\end{align*}}
The roots are real only for $\gamma \le -16$ and $\gamma \ge 0 \land \gamma \neq 2$.
We are only interested in the roots that satisfy $0 < \i_1 < 1$. The root
{\small\begin{align*}
& \frac{-\gamma-4 - \sqrt{16\gamma + \gamma^2}}{2(\gamma-2)}
\end{align*}}
is never between 0 and 1: negative for $\gamma=-16$ and decreasing as $\gamma$ decreases; equal to 1 for $\gamma=0$ and increasing for $\gamma \in [0,2)$; approaching -1 from below for $\gamma > 2$. The other root
{\small\begin{align}
& \i_1 = \frac{-\gamma-4 + \sqrt{16\gamma + \gamma^2}}{2(\gamma-2)} \label{eq:b1b2eq}
\end{align}}
is approaching zero from below for $\gamma \le -16$ as $\gamma$ decreases. This root falls into the feasible range $0 < \i_1 < 1$ for $\gamma > 0$ (undefined for $\gamma=2$): equals 1 at $\gamma=0$ and approaches zero from above as $\gamma$ increases. Therefore, only Equation~\ref{eq:b1b2eq} for $\gamma>0$ may be supporting an equilibrium. To be an equilibrium, it must satisfy Equation~\ref{eq:b1b2ineq}. We find the values of $\gamma >0$ where the condition is satisfied
{\small\begin{align*}
& [\frac{1}{2}y + \frac{1}{2} + \gamma(\frac{1}{4}y + \frac{1}{2}x)] - \frac{1}{2}(1-x-y) \ge [(-\frac{1}{2}x	+ \frac{1}{2}) + \gamma(\frac{3}{4}x + \frac{1}{2}y + \frac{1}{4})] - 1 + x + y
\end{align*}}
Replacing $x$ and $y$ according to Equations~\ref{eq:prob1}, then replacing $\i_1$ with Equation~\ref{eq:b1b2eq}, we get after simplification
{\small\begin{align*}
& \frac{5\gamma^2 + \gamma\sqrt{16\gamma+\gamma^2} -24\gamma + 16}{16(2 - \gamma)} \ge 0
\end{align*}}
Solving the resulting inequality for $\gamma$, we obtain $0<\gamma \le 2(2 - \sqrt{2})$ giving us a full characterization of equilibrium for $A'=\{(0,0)\ (1,0)\}$: the strategy $(A',\i)$ with $\i$ defined in Equation~\ref{eq:b1b2eq} is an equilibrium for $0<\gamma \le 2(2 - \sqrt{2})$.There are no other equilibria with the support $A'=\{(0,0)\ (1,0)\}$.

Equilibria for $A'= A = \{(0,0)\ (1,0)\ (1,1)\}$ and $A'=  \{(0,0)\ (1,1)\}$ are derived similarly\footnote{The algebraic derivations in this Section were performed in Mathematica 7.0~\cite{mathematica}}. The systems of equations that need to be solved are 
{\small\begin{align*}
& u(\i_1,(0,0),h(\cdot;\i)) = u(\i_1,(1,0),h(\cdot;\i))\\
& u(\i_2,(1,0),h(\cdot;\i)) = u(\i_2,(1,1),h(\cdot;\i))\\
& 0 < \i_1 < \i_2 < 1\\
& h(0,0) = \i_1 \quad\quad h(1,0) = h(0,1) = \frac{\i_2-\i_1}{2}\quad\quad h(1,1) = 1 - \i_1 - \frac{\i_2-\i_1}{2}
\end{align*}}
and
{\small\begin{align*}
& u(\i_1,(0,0),h(\cdot;\i)) = u(\i_1,(1,1),h(\cdot;\i))\\
& u(\i_1,(0,0),h(\cdot;\i)) \ge u(\i_1,(1,0),h(\cdot;\i))\\
& 0 < \i_1 < 1\\
& h(0,0) = \i_1 \quad\quad h(1,0) = h(0,1) = 0 \quad\quad h(1,1) = 1 - \i_1
\end{align*}}
respectively.

The results above show that the equilibrium for each value of $\gamma$ is unique (see Figure~\ref{fig:eq}). 

%Only interested in $\gamma > 0$.


We omit algebraic derivations and only present the solutions describing equilibria. The bids $A'= A = \{(0,0)\ (1,0)\ (1,1)\}$ support the following unique equilibrium on $2(2 - \sqrt{2})< \gamma < 2$ 
{\small\begin{align*}
& \i_1 = \frac{2 \left(2-2 \gamma+\sqrt{-\gamma^2+\gamma^3}\right)}{4-4 \gamma+\gamma^2}\\
& \i_2 = \frac{-6 \gamma^2+4 \sqrt{(-1+\gamma) \gamma^2}+2 \gamma \left(2+\sqrt{(-1+\gamma) \gamma^2}\right)}{(-2+\gamma)^2 \left(-\gamma+\sqrt{(-1+\gamma) \gamma^2}\right)}
\end{align*}}
The bids $A'= \{(0,0)\ (1,1)\}$ support the following unique equilibrium on $2 < \gamma$ 
{\small\begin{align*}
& \i_1 = \frac{-6-\gamma+\sqrt{-28+44 \gamma+\gamma^2}}{4 (-2+\gamma)}
\end{align*}}




%The technique we used to derive equilibria involves solving systems of equations quadratic in $\i$. The number of simultaneous equations is the same as the number of bids $B'$. 
%We are not aware\commentv{Zinovi, what's the best way of stating this?} of a general technique for solving simultaneous equations.
%talk about complexity as a f-n of bids/bidders/distribution.
